package com.sukaiyi.leetcode._41first_missing_positive;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * @author sukaiyi
 * @date 2020/12/27
 * @see <a href="https://leetcode-cn.com/problems/first-missing-positive">题目地址</a>
 */
public class Solution {


    @Test
    public void test() {
        Assertions.assertEquals(firstMissingPositive(new int[]{1, 1000}), 2);
        Assertions.assertEquals(firstMissingPositive(new int[]{-5, 1000}), 1);
        Assertions.assertEquals(firstMissingPositive(new int[]{1000, -1}), 1);
        Assertions.assertEquals(firstMissingPositive(new int[]{1, 2, 0}), 3);
        Assertions.assertEquals(firstMissingPositive(new int[]{3, 4, -1, 1}), 2);
        Assertions.assertEquals(firstMissingPositive(new int[]{7, 8, 9, 11, 12}), 1);
        Assertions.assertEquals(firstMissingPositive(new int[]{0, 1, 2, 3, 4, 5}), 6);
        Assertions.assertEquals(firstMissingPositive(new int[]{2147483647}), 1);
    }

    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num < 0) {
                continue;
            }
            max = Math.max(num, max);
            min = Math.min(num, min);
        }
        if (max <= 0 || min > 1) {
            return 1;
        }
        byte[] buf = new byte[nums.length / 8 + 1];
        for (int num : nums) {
            if (num > nums.length) {
                continue;
            }
            set(buf, num);
        }
        for (int i = 1; i / 8 < buf.length; i++) {
            byte b = buf[i / 8];
            int index = i % 8;
            if ((byte) (b << (7 - index)) >= 0) {
                return i;
            }
        }
        return max + 1;
    }

    private void set(byte[] buf, int num) {
        if (num < 0) {
            return;
        }
        buf[num / 8] = (byte) (buf[num / 8] | (1 << num % 8));
    }
}
